<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      封装单链表
      */

      // 创建node节点
      class Node {
        constructor (element){
          this.element = element
          this.next = null  // 指针的指向  
        }
      }

      // 封装 连接方法
      class LinkedList {
        constructor(){
          this.count = 0 // 计算链表的长度
          this.head = null  // 链头
        }
        
        // push方法
        push(data){
          // 每次push前  先实例化成为一个node节点
          const node = new Node(data)
          // 如果此时head是空
          if(this.head === null){
            this.head = node
          }else{
            // 如果不是空的情况下
            // 暂时存储一下head的元素
            let current = this.head

            /* 
            while (表达式) {
              表达式结果为真时候执行的代码;
            }
            */

            // current的next为空的时候 结束循环 也就是链表不止有一条数据的时候 进入循环 
            // console.log(current, 'current');
            while (current.next !== null){
              current = current.next
            }
            // 此时current.next 应该指向 添加的元素 node
            current.next = node
          }
          this.count++
        }

        // 在指定位置删除元素
        removeAT(index){
          if(index >= 0 && index < this.count){
            if(index === 0 ){
              this.head = this.head.next // 让next指向赋值给head
            }else{
              // 声明两个临时变量 一个用来保存上一个节点 一个用来保存当前节点 
              let previous ;
              var current = this.head ; // 当前节点

              // 进入for循环
              for(let i = 0; i < index ; i++){
                previous = current
                current = current.next
              }
              previous.next = current.next // 完成删除操作 上一个节点的next 指向 当前节点的next 
            }
            this.count--
            return current.element
          }
          return
        }

        // 将业务抽离  传入索引时 返回node节点
        getNodeAt(index){
          if(index >=0 && index < this.count){
            let node = this.head
            for(let i = 0 ; i < index; i++){
              node = node.next // 如果有多个 把node.next 赋值给node
            }
            return node
          }
          return
        }

        // 改造过后的删除
        removeAt2(index){
          if(index >= 0 && index < this.count){
            if(index === 0){
              this.head = this.head.next
            }else{
              let previous = this.getNodeAt(index-1) // 上一个节点
              var current = previous.next // 当前节点
              previous.next = current.next
            }
            this.count--
            return current.element
          }
          return
        }

        // 检查两个参数是否全等
        equalFn(a,b){
          // {a:1} === {a:1} // 结果为false 
          // 1. 判断是对象， 对象1[key] === 对象2[key]
          // 2. 之前基础上， 写一个递归函数， 深度检查是否相等
          return JSON.stringify(a) === JSON.stringify(b)
          // imumutable 库 可以迅速判断 对象或者数组是否相等（kerwin React视频）
        }

        // 抽离业务 传入element 返回索引
        indexOf(element){
          let current = this.head // 当前节点
          for(let i = 0 ; i <this.count ; i++){
            if(element === current.element){
              return i
            }
            current = current.next // 每循环一次就检查下一项
          }
          return -1
        }

        // 给定值 删除该节点
        remove(element){
          const index = this.indexOf(element) // 取得索引值 
          return this.removeAt2(index)
        }

        // 在指定位置插入值
        insert(element , index){
          if(index >= 0 && index <this.count){
            // 以传入的element 创建新节点
            const node = new Node(element)
            if(index === 0 ){
              // 当前节点
              let current = this.head
              node.next = current // 新节点的指针指向
              this.head = node // 将新节点设置为头部
            }else{
              // 获取前一节点和当前节点
              const previous = this.getNodeAt(index-1)
              const current = previous.next
              // 新节点的指针指向当前的节点
              node.next = current
              // 上一节点的指针指向node
              previous.next = node
            }
            this.count++
            return true
          }
          return false
        }

        isEmpty(){
          return this.size() === 0
        }
        size(){
          return this.count
        }
        getHead(){
          return this.head
        }
      }
    </script>
    <script>
      // 在单链表的基础上, 重写双向链表  能复用的方法就复用, 不能复用的 重写方法
      class DoublyNode extends Node{
        constructor(element){
          super(element) // 这里继承了 Node节点的  element   next  还缺少prev  
          this.prev = null
        }
      }

      class DoublyLinkedList extends LinkedList {
        constructor (){
          super()   // 继承了 count  head  
          this.tail = null 
        }
        // 必须重写
        push(element){
          const node = new DoublyNode(element)// 生成node节点
          // 然后看指针指向问题  还是分情况讨论
          if(this.head === null){
            // 链表为空的时候 都指向这个node节点
            this.head =node
            this.tail = node
          }else{
            /* 
            这里的逻辑文字讲解一下: 此时tail的next指针指向node   node的prev指针指向tail  再把此时的tail赋值给node 
            (head)   (tail)     新插入的node
              □        □ 
            */
            this.tail.next = node; 
            node.prev = this.tail;
            this.tail = node;
          }
          this.count++
        }
        // 从指定位置插入
        insert(element , index){
          if(index >= 0 && index <= this.count ){
            const node = new DoublyNode(element)
            let current = this.head // 暂时存储链表头
            // 插入元素时 分三种情况去讨论  最前面、最后面、中间
            if(index === 0){
              /// 从最前面插入元素  还是分情况 链表为空  
              if(this.head === null){
                this.head = node 
                this.tail = node
              }else{
                // 新插入的node在最前面  node的next指针指向head  head的prev指针指向node    
                node.next = this.head
                this.head.prev = node
                this.head = node
              }
            }else if (index === this.count){
              // 插入到最后面 链尾的next指向node  node的prev指向链尾  
              const current_2 = this.tail // 暂时存一下链尾 
              current_2.next = node
              node.prev = current_2
              this.tail = node
            }else{
              // 插入到中间某个元素
              const previous = this.getNodeAt(index - 1)  // 上一个节点
              const current = previous.next  // 获取当前节点
              /* 
              这里的思路是 先设置current  再设置previous 
              (previous)  新插入的node   (current)     
                  □          node            □ 
              */
              // node的next指向当前节点
              node.next = current 
              // 当前的prev指向node
              current.prev = node
              // 上一个节点的next指向node
              previous.next = node
              // 最后设置node的prev指向pervious
              node.prev = previous
            }
            this.count++
            return true
          }
          return false
        }

        removeAT(index){
          if(index >= 0 && index < this.count){
            if(index=== 0){
              this.head = this.head.next
              if(this.count === 1){
                this.tail = undefined
              }else{
                this.head.prev = undefined
              }
            }else if ( index = this.count -1 ){
              const current = this.tail
              this.tail = current.prev
              this.tail.next = undefined
            }else{
              const current = this.getNodeAt(index)
              const previous = current.prev
              previous.next = current.next
              current.next.prev = previous
            }
            this.count--
            return true
          }
          return undefined
        }
        getHead(){
          return this.head
        }
        getTail(){
          return this.tail
        }
      }

    </script>
    <script>
      // 封装循环链表
      class CirularLinkedList extends LinkedList {
        constructor(){
          super()
        }
        // 重写方法
        push( element ){
          const node = new Node(element)
          let current;
          // 还是要分情况讨论
          if( this.head === null ){
            this.head = node
          }else{
            // 获取链尾
            current = this.getNodeAt(this.size()-1)
            current.next = node  // 让链尾的next指向 指向node
          }
          // 形成循环链表
          node.next = this.head
          this.count++ 
        }

        insert(element , index){
          if(index >= 0 && index <= this.count){
            let node = new Node(element)
            // 分情况讨论
            if(index === 0){
              if(this.head === null){
                this.head = node
                node.next = this.head
              }else{
                node.next = this.head
                const last = this.getNodeAt(this.size()-1) // 获取链尾
                // console.log(last);
                this.head = node
                last.next =this.head // 链尾的next指向链头
              }
            }else{
              // 获取上一个节点 和 当前节点
              const previous = this.getNodeAt(index - 1)
              const current = previous.next
              // 将node 插入
              node.next = current
              previous.next = node
            }
            this.count ++
            return true
          }else{
            return false
          }
        }

        removeAT(index){
          if(index >= 0 && index <= this.count){
            let current = this.head
            if(index === 0){
              // 处理临界情况 
              if(this.size() === 1){
                this.head = undefined
              }else{
                const last = this.getNodeAt(this.size()-1) // 获取链尾
                this.head = this.head.next
                last.next = this.head
              }
            }else{
              // 获取上一个节点和当前节点
              const previous = this.getNodeAt(index - 1)
              current = previous.next
              previous.next = current.next
            }
            this.count --
            return current.element 
          }else{
            return 
          }
        }



      }

      var list = new CirularLinkedList()
    </script>
  </body>
</html>
